package 剑指offer.堆栈队列;

import java.util.Stack;

/**
 * 设置 S1 和 S2 两个栈，S1 负责接收数据，入栈，模拟队列的 append 操作
 * 出队列时，把 S1 全部 pop 到 S2，此时 S2 再 pop 出去的数据就是最先进入的数据
 * 当然，要先确保 S2 是空的才能把 S1 的数据加入进去
 */
public class 第9题用两个栈实现一个队列 {

    static class TQZUQueue<T> {
        private Stack<T> s1 = new Stack<>();
        private Stack<T> s2 = new Stack<>();

        // 实现往队列尾上添加元素
        public void append(T val) {
            // s1 负责接收 append 的元素
            s1.push(val);
        }

        // 实现在队列头部删除元素
        public T delete() {
            // s2 负责删除队列首部的元素
            if (!s2.empty()) {
                return s2.pop();
            } else {
                while (!s1.empty()) {
                    s2.push(s1.pop());
                }
                return s2.pop();
            }
        }
    }

    public static void main(String[] args) {
        TQZUQueue<String> queue = new TQZUQueue<>();
        queue.append("a");
        queue.append("b");
        queue.append("c");
        System.out.println(queue.delete());
        System.out.println(queue.delete());
        System.out.println(queue.delete());
        System.out.println("==== 再添加一个元素 d、e ");
        queue.append("d");
        queue.append("e");
        System.out.println(queue.delete());
    }
}
